package com.leetcode.No0878;

import org.junit.Test;

import java.math.BigInteger;

/**
 * @program: Solution
 * @description: 第 N 个神奇数字
 * @author: Wang Zhihua
 * @date: 2022-11-25
 */
public class Solution2 {

    private long targetN;
    private int numA;
    private int numB;
    private int minCommonMultiple;
    private long mod = 1000000007L;

    public int nthMagicalNumber(int n, int a, int b) {
        targetN = n;
        numA = a;
        numB = b;
        minCommonMultiple = calMinCommonMultiple(a, b);
        long left = Math.min(a, b);
        long right = targetN * left;
        return (int) (findMid(left, right) % mod);
    }

    private long findMid(long left, long right) {
        long mid = (left + right) >> 1;
        long idx = calCurrentIdx(mid);
        if (idx < targetN) {
            return findMid(mid + 1, right);
        } else if (idx > targetN) {
            return findMid(left, mid - 1);
        } else {
            while (mid % numA > 0 && mid % numB > 0) {
                --mid;
            }
            return mid;
        }
    }

    private long calCurrentIdx(long num) {
        return num/numA + num/numB - num/minCommonMultiple;
    }

    /**
     * 求 a 和 b 的最小公倍数
     * 因为 a 和 b 最大40000，所以因数最大200
     */
    private int calMinCommonMultiple(int a, int b) {
        int minCommonMultiple = 1;
        for (int i = 2; i <= 200; ++i) {
            while (a % i == 0 && b % i == 0) {
                a /= i;
                b /= i;
                minCommonMultiple *= i;
            }
        }
        return minCommonMultiple * a * b;
    }

    @Test
    public void test01() {
        int n, a, b;

        n = 1;
        a = 2;
        b = 3;
        System.out.println(nthMagicalNumber(n, a, b));

        n = 4;
        a = 2;
        b = 3;
        System.out.println(nthMagicalNumber(n, a, b));

        n = 5;
        a = 2;
        b = 4;
        System.out.println(nthMagicalNumber(n, a, b));

        n = 8;
        a = 10;
        b = 5;
        System.out.println(nthMagicalNumber(n, a, b));

        n = 1000000000;
        a = 39999;
        b = 40000;
        System.out.println(nthMagicalNumber(n, a, b));

        n = 307673195;
        a = 37340;
        b = 36427;
        System.out.println(nthMagicalNumber(n, a, b));
    }
}
